package com.dq.utils;

public class KMP {
    public static void main(String[] args) {
        String s1 = "abcdedab";
        String s2 = "deda";
        System.out.println(kmp(s1, s2));

    }
    public static int kmp(String s, String t){
        if(t.equals("")) return 0;
        if(s.length() < t.length()) return -1;
        int[] next = getNext(t);
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()){
            if(j == -1 || s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        return j == t.length() ? i - j : -1;
    }
    private static int[] getNext(String t){
        int[] next = new int[t.length()];

        int i = 0, j = -1;
        next[0] = -1;

        while (i < t.length()-1){
            if(j == -1 || t.charAt(i) == t.charAt(j)){
                i++;
                j++;
                next[i] = j;
            }else{
                j = next[j];
            }
        }

        return next;
    }
}
